package basic.study.wantOffer.chapter5;

import java.lang.reflect.Array;
import java.util.ArrayList;

/**
 * @ClassName Problem57
 * @Description 和为S的两个数字
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/13 15:22
 * @Version 1.0
 */
public class Problem57 {
    public ArrayList<Integer> FindNumbersWithSum(int[] arr, int sum) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        int startIndex = 0;
        int endIndex = arr.length - 1;
        ArrayList<Integer> list = new ArrayList<>();

        while (startIndex < endIndex) {
            if (arr[startIndex] + arr[endIndex] == sum) {
                list.add(arr[startIndex]);
                list.add(arr[endIndex]);
                break;
            } else if (arr[startIndex] + arr[endIndex] > sum) {
                endIndex--;
            } else {
                startIndex++;
            }
        }
        if (startIndex >= endIndex) {
            return null;
        } else {
            return list;
        }
    }

    /**
     * 为s的连续正数序列
     * 解法一：采用双指针法（见下面代码）
     * 解法二：数学分析法   https://www.cnblogs.com/yongh/p/9962159.html
     */
    class Problem57_2 {
        public ArrayList<ArrayList<Integer>> FindContinuesSequences(int sum) {
            ArrayList<ArrayList<Integer>> list = new ArrayList<>();
            if (sum <= 0) {
                return list;
            }
            int small = 1;
            int big = 2;
            int curSum = small + big;
            while (small <= sum / 2) {
                if (curSum == sum) {
                    ArrayList<Integer> sequence = new ArrayList<>();
                    for (int i = small; i <= big; i++) {
                        sequence.add(i);
                    }
                    list.add(sequence);
                    curSum -= small;
                    small++;//这两行先后位置要注意
                } else if (curSum < sum) {
                    big++;
                    curSum += big;
                } else {
                    curSum -= small;
                    small++;
                }
            }
            return list;
        }
    }
}
